package Hamierdun;

import DFS.Graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HamiltonLoop {
    private Graph graph;
    private int[] pre;
    private int end;

    public HamiltonLoop(Graph graph) {
        this.graph = graph;
        int visited = 0;
        pre = new int[graph.getVertexNum()];
        end = -1;
        dfs(visited,0, 0, graph.getVertexNum());
    }

    private boolean dfs(int visited,int v, int parent, int left) {
        visited += (1 << v);
        pre[v] = parent;
        left--;
        if (left == 0 && graph.hasEdge(v, 0)) {
            end = v;
            return true;
        }
        for (int w : graph.adj(v)) {
            if ((visited & (1 << w)) == 0) {
                if (dfs(visited,w, v, left)) {
                    return true;
                }
            }
        }
        visited -= (1 << v);
        return false;
    }

    public List<Integer> result() {
        List<Integer> res = new ArrayList<>();
        if (end == -1) {
            return res;
        }
        int cur = end;
        while (cur != 0) {
            res.add(cur);
            cur = pre[cur];
        }
        res.add(0);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] a) {
        Graph graph = new Graph("HmG.txt");
        HamiltonLoop hl = new HamiltonLoop(graph);
        System.out.println(hl.result());
        Graph graph2 = new Graph("HmG2.txt");
        HamiltonLoop hl2 = new HamiltonLoop(graph2);
        System.out.println(hl2.result());

    }
}
